package main

import "fmt"

func main() {
	fmt.Println(majorityElement2([]int{1, 2, 3, 2, 4, 2, 5, 2, 3}))
}

// Boyer-More算法
func majorityElement2(nums []int) int {
	count, candidate := 0, 0
	for _, v := range nums {
		if count == 0 {
			candidate = v
		}
		if candidate == v {
			count = count + 1
		} else {
			count = count - 1
		}
	}
	return candidate
}

func majorityElement(nums []int) int {
	m := make(map[int]int, 0)

	for _, n := range nums {
		m[n] = m[n] + 1
	}

	maxN, maxV := 0, 0
	for k, v := range m {
		if maxV < v {
			maxV = v
			maxN = k
		}
	}
	return maxN
}
